package com.lw.leetcode.binary.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 719. 找出第 K 小的数对距离
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/15 9:28
 */
public class SmallestDistancePair {

    public static void main(String[] args) {
        SmallestDistancePair test = new SmallestDistancePair();

        // 0
//        int[] arr = {1,3,1};
//        int k = 1;

        // 0
//        int[] arr = {1, 1, 1};
//        int k = 1;

        // 5
//        int[] arr = {1, 6, 1};
//        int k = 2;

        // 5
//        int[] arr = Utils.getArr(10000, 0, 1000001);
//        int k = 5000 * 9999;

        // 5
        int[] arr = {823749, 957616, 346989, 690899, 582404, 280927, 263646, 608887, 424697, 523542, 184877, 843273, 96281, 834595, 184400, 461572, 788797, 459520, 434292, 602263, 980989, 3144, 313765, 861148, 939354, 49234, 775316, 9972, 110071, 223804, 523168, 464578, 956003, 494920, 958742, 84337, 12313, 796595, 335569, 912352, 493985, 747102, 487641, 606376, 820958, 767599, 511095, 683750, 72851, 108097, 659954, 258784, 858265, 567053, 165002, 953655, 734343, 833477, 154407, 492144, 172226, 146806, 498600, 844333, 697876, 74547, 334941, 227678, 916108, 500005, 205526, 40234, 219544, 137206, 105326, 86469, 211297, 808707, 843056, 210706, 125946, 268263, 777885, 984125, 793203, 756726, 7396, 923583, 782785, 884362, 634936, 694556, 443899, 193736, 902029, 251838, 830832, 942518, 279834, 265952, 138483, 981504, 732173, 149991, 356889, 451145, 114222, 728961, 64035, 318530, 554085, 804333, 875101, 248793, 819374, 756816, 532606, 220428, 461954, 99203, 228569, 859464, 609314, 877918, 564173, 350271, 122044, 494667, 802484, 334307, 304463, 560719, 295588, 771549, 285995, 996461, 526397, 374871, 825559, 208010, 434720, 628845, 328222, 26307, 31097, 540825, 586125, 102187, 923533, 703230, 55128, 682218, 827782, 868396, 952317, 60750, 736032, 925270, 976152, 77803, 344685, 58193, 780271, 573603, 107403, 701170, 780395, 922777, 815967, 940994, 723695, 627809, 36967, 942793, 572716, 291800, 268168, 486971, 884368, 746168, 767577, 755171, 209234, 941929, 383225, 874631, 223791, 125752, 31187, 128549, 139156, 582226, 626572, 434425, 439989, 745025, 660365, 990146, 503086, 882169, 2677, 778399, 546571, 739403, 766905, 531810, 174791, 54139, 256014, 420366, 426703, 958268, 314968, 324007, 106447, 542551, 948919, 24021, 657335, 388026, 866264, 704731, 985732, 311148, 277099, 841455, 776458, 782031, 413874, 40835, 819858, 325487, 826540, 927544, 223238, 490526, 64589, 217382, 326506, 84312, 807210, 675911, 124019, 274496, 410817, 162022, 621836, 124073, 451613, 276341, 349585, 398012, 547200, 371697, 247759, 906759, 735499, 547213, 488895, 857453, 38698, 673677, 429038, 526223, 977130, 188740, 690553, 261914, 223306, 803784, 395020, 111492, 470557, 606893, 95741, 587649, 538388, 97164, 916702, 70753, 2191, 298376, 430226, 555240, 559732, 430099, 212471, 137423, 977762, 45161, 987056, 601977, 211275, 781119, 741585, 154582, 239381, 747541, 840333, 577187, 925469, 651271, 439636, 144236, 653300, 3047, 319970, 967949, 785804, 220874, 584833, 921301, 418395, 546067, 580819, 237101, 541165, 705662, 324990, 347839, 997187, 300974, 424611, 650465, 116743, 659380, 962658, 651810, 583131, 829574, 902344, 377412, 822475, 281170, 403134, 188366, 215860, 578502, 615844, 734791, 732519, 961526, 380465, 929478, 973669, 917578, 370152, 976124, 426323, 103376, 393732, 877151, 774612, 189996, 258166, 998759, 862957, 678162, 874807, 338338, 818091, 108092, 757096, 702213, 729658, 654110, 363947, 442475, 491502, 486533, 35945, 500162, 902062, 950833, 255006, 887948, 278251, 863219, 931594, 904078, 809378, 264407, 234030, 678637, 490982, 130669, 239316, 53126, 367422, 68645, 604475, 866438, 218177, 207932, 485269, 934534, 455979, 436029, 294910, 870949, 824678, 661707, 874298, 622447, 360194, 621738, 146335, 241437, 251522, 33577, 825815, 781426, 134328, 597017, 254053, 759474, 979004, 87388, 665363, 392593, 952969, 242560, 979438, 287142, 646498, 991992, 232447, 489116, 982496, 785266, 531242, 42683, 103559, 198530, 404030, 280225, 406666, 230509, 502665, 902689, 934817, 460054, 798867, 650008, 562015, 470617, 330594, 894831, 529333, 356940, 140643, 321809, 835984, 912305, 944138, 487426, 806298, 959708, 117600, 693719, 673643, 725859, 446678, 840132, 162352, 911069, 218240, 318851, 877907, 884423, 291516, 829106, 276124, 969645, 252087, 348961, 376856, 847084, 96949, 380818, 39372, 135747, 640731, 160353, 71033, 304084, 592831, 828252, 99963, 114892, 141095, 243867, 733486, 312947, 871423, 210789, 754904, 549630, 198065, 70860};
//        int[] arr = {823749,957616,346989,690899,582404,280927,263646,608887,424697,523542,184877,843273,96281,834595,184400,461572,788797,459520,434292,602263,980989,3144,313765,861148,939354,49234,775316,9972,110071,223804,523168,464578,956003,494920,958742,84337,12313,796595,335569,912352,493985,747102,487641,606376,820958,767599,511095,683750,72851,108097,659954,258784,858265,567053,165002,953655,734343,833477,154407,492144,172226,146806,498600,844333,697876,74547,334941,227678,916108,500005,205526,40234,219544,137206,105326,86469,211297,808707,843056,210706,125946,268263,777885,984125,793203,756726,7396,923583,782785,884362,634936,694556,443899,193736,902029,251838,830832,942518,279834,265952,138483,981504,732173,149991,356889,451145,114222,728961,64035,318530,554085,804333,875101,248793,819374,756816,532606,220428,461954,99203,228569,859464,609314,877918,564173,350271,122044,494667,802484,334307,304463,560719,295588,771549,285995,996461,526397,374871,825559,208010,434720,628845,328222,26307,31097,540825,586125,102187,923533,703230,55128,682218,827782,868396,952317,60750,736032,925270,976152,77803,344685,58193,780271,573603,107403,701170,780395,922777,815967,940994,723695,627809,36967,942793,572716,291800,268168,486971,884368,746168,767577,755171,209234,941929,383225,874631,223791,125752,31187,128549,139156,582226,626572,434425,439989,745025,660365,990146,503086,882169,2677,778399,546571,739403,766905,531810,174791,54139,256014,420366,426703,958268,314968,324007,106447,542551,948919,24021,657335,388026,866264,704731,985732,311148,277099,841455};
        int k = 62500;
        System.out.println(k);

        int i = test.smallestDistancePair(arr, k);
        System.out.println(i);
    }
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int length = nums.length;
        int st = 0;
        int end = nums[length - 1] - nums[0];
        long v = 0;
        while (st <= end) {
            int m = st + ((end - st) >> 1);
            v = find(nums, m + 1);
            int c = (int) v;
            if (c == k || st == end) {
                break;
            }
            if (c < k) {
                st = m + 1;
            } else {
                end = m;
            }
        }
        return (int) (v >> 32);
    }

    private long find(int[] arr, int t) {
        int count = 0;
        int length = arr.length;
        int max = 0;
        for (int i = 1; i < length; i++) {
            int f = arr[i];
            if (f - arr[i - 1] >= t) {
                continue;
            }
            int st = 0;
            int end = i - 1;
            while (st < end) {
                int m = st + ((end - st) >> 1);
                if (f - arr[m] >= t) {
                    st = m + 1;
                } else {
                    end = m;
                }
            }
            count += i - st;
            max = Math.max(max, f - arr[st]);
        }
        return ((long) max << 32) + count;
    }

}
